package primary.code05_Tree;

import java.util.Stack;

/**
 * @author Yudi Wang
 * @date 2021/7/13 17:09
 * <p>
 * 将一条纸带对折 n 次后，按照折痕的凹凸进行打印
 * <p>
 * 每次对折后，新产生的折痕可以构成二叉树的新一层，且左节点为凹，右节点为凸
 * 方式1：广度优先遍历，构建树，然后采用中序遍历打印
 * 方式2：虚构树，中序遍历
 */
public class Code11_HalfFold {

    /**
     * @param n 对折次数
     */
    public static void printHalfFold(int n, int level, boolean p) {
        if (level > n) return;
        printHalfFold(n, level + 1, true);
        System.out.print(p ? "凹" : "凸");
        printHalfFold(n, level + 1, false);
    }

    public static void printHalfFoldTest(int n) {
        if (n == 0) return;
        Stack<Node> stack = new Stack<>();
        Node cur = new Node("凹", 1);
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.level < n ? new Node("凹", cur.level + 1) : null;
            } else {
                cur = stack.pop();
                System.out.print(cur.da);
                cur = cur.level < n ? new Node("凸", cur.level + 1) : null;
            }
        }
    }

    static class Node {
        public String da;
        public int level;

        public Node(String da, int level) {
            this.da = da;
            this.level = level;
        }
    }

    public static void printHalfFoldTest2(int n, String data, int level) {
        if (n == 0 || level > n) return;
        printHalfFoldTest2(n, "凹", level + 1);
        System.out.print(data);
        printHalfFoldTest2(n, "凸", level + 1);
    }

    public static void main(String[] args) {
        printHalfFold(3, 1, true);
        System.out.println();
        printHalfFoldTest(3);
        System.out.println();
        printHalfFoldTest2(3, "凹", 1);
        System.out.println();
    }
}
